Cardinality of Power Set is Greater

Proof

It is clear that there exists an injection $S\to \mathcal{P}(S)$ given by the mapping $a\mapsto \{a\}$.

Suppose we have a function $f:S\to \mathcal{P}(S)$. We will show that such a function cannot be surjective, and thus by this result that there cannot be an injective function from $\mathcal{P}(S)$ to $S$.

Consider the set

that is, the set of elements in the input space which are mapped to a set not containing themself. We will prove that $f$ is not surjective by showing that $A$ is not in the image of $f$.

Suppose, by way of contradiction, that $f(a)=A$ for some $a\in S$. This means that

by definition of $A$, a contradiction.